The invention relates generally to the input of user information into computer systems, and more particularly to the recognition of handwritten characters input by a user.
Many handwritten characters resemble others, for example, a handwritten lowercase letter xe2x80x9coxe2x80x9d resembles a xe2x80x9c0xe2x80x9d (zero) as well as an uppercase xe2x80x9cO.xe2x80x9d Moreover, the shape of any handwritten character typically varies from user to user, and often varies from instance to instance when written by a single user. Consequently, in addition to shape matching, the accuracy of handwritten character recognition is improved when the character is also analyzed with respect to its context. Indeed, some Japanese symbols are virtually indistinguishable from one another absent surrounding context.
Context-based recognition is done in one of two ways, i.e., a backward context approach or a full context approach. Backward context recognition analyzes previous characters, if any, to determine the best translation of the current character. A benefit of backward context recognition is that each entered character is recognized and immediately displayed for user verification. In contrast, a full context approach looks at the characters both before and after each character in a string to help in the recognition thereof.
Backward context recognition is less accurate than full context recognition because by only looking backwards, only half of the available context is used. By way of example, a handwritten string such as xe2x80x9c|O0xe2x80x9d may be intended to be xe2x80x9cone-zero-zeroxe2x80x9d or the first three letters of a word such as xe2x80x9cloops.xe2x80x9d As can be appreciated, both are reasonably probable. If the next character was available for analysis, the chance of correctly recognizing the string may be greatly improved. For example, a xe2x80x9c5xe2x80x9d would strongly indicate that the first three characters were part of a number (xe2x80x9c1005xe2x80x9d) while a xe2x80x9cpxe2x80x9d would strongly indicate the first three characters were part of a word (xe2x80x9cloopxe2x80x9d). However, the backwards context recognition has to make its initial decision based solely on the first character, which may be incorrect, particularly if the character shape is one which closely resembles the shape of one or more other characters. Thereafter, subsequent characters are analyzed relative to this initial guess, e.g., a letter more likely follows a letter than a number. As can be appreciated, if the initial guess is incorrect, with backwards context recognition, some or all subsequent characters may be also incorrect, further compounding the error.
Full (forwards and backwards) context recognition is thus more accurate than backwards recognition because of the ability to use all rather than half of the available context information. A first approach to full context recognition is to wait for the user to complete all characters in a given string (with the user indicating completion) and then analyze the full string. Full context thus provides a relatively high level of recognition accuracy, but also has a number of drawbacks associated therewith. First, the user receives no feedback while entering the characters until the user indicates that the string is complete. Second, there is a noticeably long delay between receipt of the string and the completion of the recognition operation. Lastly, and possibly most important, the memory requirements for keeping a potentially unlimited amount of electronic ink in the memory for a potentially unlimited amount of characters would overwhelm many systems, particularly hand-held (palmtop) computing devices in which handwriting recognition is commonplace.
A compromise solution has been attempted in which backwards context recognition is initially performed to provide instantaneous feedback using only small amounts of memory, while full context recognition is later performed on those backwards-recognized characters to increase recognition accuracy. However, this solution has the effect of changing characters that have already been displayed, and possibly verified as correct by the user, to character values that may be incorrect. Indeed, in most cases, unilaterally changing a character after display and verification of the correctness thereof has been found so annoying to users that this is an unacceptable solution, even though overall recognition accuracy may be increased.
Accordingly, it is a general object of the present invention to provide an improved method and mechanism for performing full-context recognition.
Another object is to provide a full context recognition method and mechanism that facilitates rapid visual feedback while having relatively low memory requirements.
In accomplishing those objects, it is a related object to provide a method and mechanism as characterized above that functions with existing recognition components such as shape matching components and language model context components.
Yet another object is to provide a method and mechanism of the above kind that is fast, reliable, cost-efficient, flexible and extensible.
Briefly, the present invention provides a method and mechanism for recognizing handwritten characters previously entered into the system from the context of subsequent handwritten characters presently being entered into the system. Using a shape matcher, each handwritten character entered is associated with a plurality of alternate code points therefor, with each alternate code point having probability information associated therewith. As each character is received, the alternate code points therefor are placed at the end of a queue, and a cost is determined from each alternate code point to any immediately preceding alternate in the queue. The cost is based on the probability information of the alternates and a transition cost therebetween. Then, the lowest cost path back from each of the alternates at the end of the queue to an alternate at the beginning of the queue is determined. If each lowest cost path back converges at (traverses) a common alternate in the queue, the common alternate and any alternates previous thereto on the path back are recognized as the code points for each of the handwritten characters associated therewith. The alternates corresponding to recognized code points are removed from the queue, and the code points appropriately displayed on a screen as recognized characters, to allow editing thereof or the like.
Other objects and advantages will become apparent from the following detailed description when taken in conjunction with the drawings, in which: